package com.zhangx.datastructure.graph;

import java.util.Arrays;

/**
 * 最短路径
 */
public class ShorestPath {

    int MAXVEX = 9;
    int INFINITY = 65536;
//    最短路径的下标
    int[] pathArc = new int[MAXVEX];
//    到各点的最短路径权值和
    int[] shortPathTable = new int[MAXVEX];

    //    最短路径的下标
    int[][] pathArcFloyd = new int[MAXVEX][MAXVEX];
    //    到各点的最短路径权值和
    int[][] shortPathTableFloyd = new int[MAXVEX][MAXVEX];


    //    顶点
    Vertex[] vexs = new Vertex[MAXVEX];
    int numVertexes = 9;//顶点数
    //    邻接矩阵
    int[][] arc = new int[MAXVEX][MAXVEX];

    int[][] D_1 = new int[MAXVEX][MAXVEX];
    int[][] P_1 = new int[MAXVEX][MAXVEX];

    /**
     * 顶点
     */
    class Vertex{

        private String data;

        public Vertex(String data){
            this.data = data;
        }

        @Override
        public String toString() {
            return "Vertex{" +
                    "data='" + data + '\'' +
                    '}';
        }
    }
    /**
     * 构建邻接矩阵
     */
    public void init(){
//        ---------------构建邻接矩阵----------------
//        9个点
        for (int i = 0; i < 9; i++) {
            vexs[i] = new Vertex("V"+i);
        }
        numVertexes = 9;
        int[] a0 = new int[]{0,1,5,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY};
        int[] a1 = new int[]{1,0,3,7,5,INFINITY,INFINITY,INFINITY,INFINITY};
        int[] a2 = new int[]{5,3,0,INFINITY,1,7,INFINITY,INFINITY,INFINITY};
        int[] a3 = new int[]{INFINITY,7,INFINITY,0,2,INFINITY,3,INFINITY,INFINITY};
        int[] a4 = new int[]{INFINITY,5,1,2,0,3,6,9,INFINITY};
        int[] a5 = new int[]{INFINITY,INFINITY,7,INFINITY,3,0,INFINITY,5,INFINITY};
        int[] a6 = new int[]{INFINITY,INFINITY,INFINITY,3,6,INFINITY,0,2,7};
        int[] a7 = new int[]{INFINITY,INFINITY,INFINITY,INFINITY,9,5,2,0,4};
        int[] a8 = new int[]{INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,7,4,0};

        arc[0] = a0;
        arc[1] = a1;
        arc[2] = a2;
        arc[3] = a3;
        arc[4] = a4;
        arc[5] = a5;
        arc[6] = a6;
        arc[7] = a7;
        arc[8] = a8;

        System.out.println("  V0 V1 V2 V3 V4 V5 V6 V7 V8");
        for (int i = 0; i < arc.length; i++) {
            String line = "v"+i;
            for (int j = 0; j < arc[i].length; j++) {
                line = line + " " + arc[i][j];
            }
            System.out.println(line);
        }
//        floyd算法使用
        D_1 = arc;
        for (int i = 0; i < D_1.length; i++) {
            int[] p = new int[]{0,1,2,3,4,5,6,7,8,9};
            P_1[i] = p;
        }

        System.out.println("  V0 V1 V2 V3 V4 V5 V6 V7 V8");
        for (int i = 0; i < P_1.length; i++) {
            String line = "v"+i;
            for (int j = 0; j < P_1[i].length; j++) {
                line = line + " " + P_1[i][j];
            }
            System.out.println(line);
        }


    }
    /**
     * 迪杰斯特拉 算法
     * 求最短路径P[v]及其权长度D[v]
     */
    void dijkstra(int v0){
        int[] fin = new int[MAXVEX];//v0到v?的最短路径
        for (int v = 0; v < numVertexes; v++) {
            fin[v] = 0;
            shortPathTable[v] = arc[v0][v];//与v0有连线的节点记录权值
            pathArc[v] = 0;
        }
        shortPathTable[v0] = 0;//v0到v0是0
        fin[v0] = 1;//以求得
        int k = 0;
        int min = 0;
//        依次求得v0到其余每个节点的最短路径,因此从1开始循环
        for (int v = 1; v < numVertexes; v++) {
            min = INFINITY;
//            找距离v0最近的顶点
            for (int w = 0; w < numVertexes; w++) {
//                没计算+有路径，当V=1找到的是k=1,min=1
                if (fin[w]!=1 && shortPathTable[w]<min){
                    k = w;
                    min = shortPathTable[w];//w与v0 更近
                }
            }
            fin[k] = 1;
            for (int w = 0; w < numVertexes; w++) {
//                修正数据 如果经过v 的路径比现在路径短
//                min是v0->vx，判断v0->vx->v[x+1]与v0->v[x+1]比较
                int x = min+arc[k][w];
                if (fin[w]!=1 && (x<shortPathTable[w])){
                    shortPathTable[w] = min + arc[k][w];//修改路径长度
                    pathArc[w] = k;//所以到达v[w]的最短路径是k->w
                }
            }
        }
        System.out.println(Arrays.toString(shortPathTable));
//        到达index节点的最短前驱
        System.out.println(Arrays.toString(pathArc));
    }

    /**
     * 弗洛伊德算法
     * 求最短路径P及带权长度D
     */
    void floyd(){
        int[] fin = new int[MAXVEX];//v0到v?的最短路径
//        初始化数据
        for (int v = 0; v < numVertexes; ++v) {
            for (int w = 0; w < numVertexes; ++w) {
                shortPathTableFloyd[v][w] = arc[v][w];
                pathArcFloyd[v][w] = w;
            }
        }

//        k 中转顶点，要拿出每个顶点，循环整个矩阵计算出最短的路径
        for (int k = 0; k < numVertexes; ++k) {
//            v起始顶点
            for (int v = 0; v < numVertexes; ++v) {
//                w结束顶点
                for (int w = 0; w < numVertexes; ++w) {
//                    如果经过下标k的路径比两点间直连更短
//                    v-k-w比v-w更近
                    if (shortPathTableFloyd[v][w]>(shortPathTableFloyd[v][k]+shortPathTableFloyd[k][w])){
                        shortPathTableFloyd[v][w] = shortPathTableFloyd[v][k]+shortPathTableFloyd[k][w];
//                        路径里面要记录k  v->w变为v->k
                        pathArcFloyd[v][w] = pathArcFloyd[v][k];
                    }
                }
            }
        }

        System.out.println("  V0 V1 V2 V3 V4 V5 V6 V7 V8");
        for (int i = 0; i < shortPathTableFloyd.length; i++) {
            String line = "v"+i;
            for (int j = 0; j < shortPathTableFloyd[i].length; j++) {
                line = line + " " + shortPathTableFloyd[i][j];
            }
            System.out.println(line);
        }
        System.out.println("  V0 V1 V2 V3 V4 V5 V6 V7 V8");
        for (int i = 0; i < pathArcFloyd.length; i++) {
            String line = "v"+i;
            for (int j = 0; j < pathArcFloyd[i].length; j++) {
                line = line + " " + pathArcFloyd[i][j];
            }
            System.out.println(line);
        }
    }

    public static void main(String[] args) {
        ShorestPath shorestPath = new ShorestPath();
        shorestPath.init();
        shorestPath.dijkstra(0);
        shorestPath.floyd();
    }


}
